package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * 687. 最长同值路径
 * @author feizns
 * @since 2020/1/4
 */
public class LongestUnivaluePath {

    public static void main(String[] args) {
        System.out.println(new LongestUnivaluePath().longestUnivaluePath(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(5);
        ret.right = new TreeNode(5);
        ret.right.left = new TreeNode(5);
        ret.left = new TreeNode(4);
        ret.left.left = new TreeNode(1);
        ret.left.right = new TreeNode(1);
        return ret;
    }

    int ans;

    public int longestUnivaluePath(TreeNode root) {
        helper(root);
        return ans;
    }

    private int helper(TreeNode root) {
        if ( root != null ) {
            int l = helper(root.left);
            int r = helper(root.right);
            l = (root.left != null && root.left.val == root.val) ? l + 1 : 0;
            r = (root.right != null && root.right.val == root.val) ? r + 1 : 0;
            ans = Math.max(ans, l + r);
            return Math.max(l, r);
        }
        return 0;
    }

//    private static int max = 0;
//
//    public static int longestUnivaluePath(TreeNode root) {
//        preOrder(root);
//        return max;
//    }
//
//    private static void preOrder(TreeNode root) {
//        if ( root != null ) {
//            int path = path(root);
//            if ( path > max )
//                max = path;
//            preOrder(root.left);
//            preOrder(root.right);
//        }
//    }
//
//    private static int path(TreeNode root) {
//        if ( root != null ) {
//            int lH = height(root.left, root.val);
//            int rH = height(root.right, root.val);
//            return lH + rH;
//        }
//        return 0;
//    }
//
//    private static int height(TreeNode root, int val) {
//        if ( root != null && root.val == val ) {
//            int left = height(root.left, val);
//            int right = height(root.right, val);
//            return Math.max(left, right) + 1;
//        }
//        return 0;
//    }

}
